package com.java.comprehensive.arithmetic.leecode.tags.array;

/**
 * @Author: 窦绍飞
 * @Date: 2022/6/27
 */
public class LeetCode_33 {

	public static int search(int[] nums, int target) {
		int result = -1;
		int n = nums.length;
		int i = 0, j = n - 1;
		while (i <= j) {
			int mid = (i + j) / 2;

			if (nums[mid] == target) return mid;
			if (nums[i] == target) return i;
			if (nums[j] == target) return j;

			//如果mid >i 那么 i->mid 之间就是有序
			//如果mid <i 那么 i->mid 之间只能是部分有序
			if (nums[i] < nums[mid]) {
				//如果有一个大于target 就从左边找 否则从右边找
				if (nums[i] < target && nums[mid] > target) {
					j = mid - 1;
				} else {
					i = mid + 1;
				}
			} else {
				//在这如果前面不是有序 后面就是有序 看看有序的有没有然后重复 这么做来找到对应的target下标
				if (nums[mid] < target && nums[j] > target) {
					i = mid + 1;
				} else {
					j = mid - 1;
				}
			}
		}
		return result;
	}

	public static void main(String[] args) {
		int[] nums = {8, 1, 2, 3, 4, 5, 6, 7};
		System.out.println(search(nums, 6));
	}
}
